/*
 * @Description:二叉搜索树 先序 后续 中序二叉树  
 * @Version: 1.0
 * @Autor: ziwei
 * @Date: 2021-04-15 09:16:32
 * @LastEditors: ziwei
 * @LastEditTime: 2021-04-15 15:36:10
 */

class Node {
    //创建节点要告诉我 元素和爸爸
    constructor(element, parent) {
        this.element = element;
        this.parent = parent;//标记父节点
        this.left = null;//左边
        this.right = null;
    }
}

class Tree {//二叉搜索树 我们没有考虑相同值的情况
    constructor() {
        this.root = null;//默认空树
    }

    add(element) {
        if (this.root == null) {//树根
            return this.root = new Node(element);
        }

        //可以用递归 用循环就可以了
        let currentNode = this.root;//更新当前更节点
        let parent;
        let compare;
        while (currentNode) {
            compare = currentNode.element < element;
            parent = currentNode;
            if (compare) {
                currentNode = currentNode.right
            } else {
                currentNode = currentNode.left;
            }
        }

        let newNode = new Node(element, parent);
        if (compare) {
            parent.right = newNode
        } else {
            parent.left = newNode;
        }
    }
    
    //先序
    preOrderTraversal(){
      function traversal(node) {
        if(node == null) return;
        console.log(node.element);
        traversal(node.left);
        traversal(node.right);
      }
      traversal(this.root);
    }
    
    //中序
    inOrderTraversal(){
      function traversal(node) {
        if(node == null) return
        traversal(node.left);
        console.log("中序",node.element);
        traversal(node.right);
      }
      traversal(this.root);
    }

    //后序
    postOrderTraversal(){
      function traversal(node) {
        if(node == null) return
        traversal(node.left);
        traversal(node.right);
        console.log("后序",node.element);
      }
      traversal(this.root);
    }

    //层序 维护一个栈 指针不断的往往后指
    levelOrderTraversal(){
      let stack = [this.root];
      let index = 0;
      let currentNode;
      while (currentNode = stack[index++]) {
        console.log(currentNode);
        if(currentNode.left){
          stack.push(currentNode.left);
        }
        if(currentNode.right){
          stack.push(currentNode.right);
        }
      }
    }
    

    //反转二叉树
    reverse(){
      let stack = [this.root];
      let index = 0;
      let currentNode;
      while (currentNode = stack[index++]) {
        let temp = currentNode.left;
        currentNode.left = currentNode.right;
        currentNode.right = temp;
        if(currentNode.left){
          stack.push(currentNode.left);
        }
        if(currentNode.right){
          stack.push(currentNode.right);
        }
      }
    }
}

// let tree = new Tree();
// [10, 8, 19, 6, 15, 22, 20].forEach(i => {
//     tree.add(i)
// })
// //console.dir(tree, { depth: 100 })
// tree.preorderTraversal()
//关键代码在24-42 
// 1:一个类Node 上有自己 左右和爸爸4个属性
//用while循环 找出我应该被插入到哪个父亲节点下 分左边和右边: 找到父亲和 判断左边还是右边的标志
//找到后进行插入

// 遍历树：（递归 非递归 =》栈优化）
//先序 中序 后序 层序
module.exports = Tree